package com.lz.tree;

import com.lz.tree.common.Node;
import com.lz.tree.common.TreeNode;

import java.util.*;


public class Leetcode {
    public static void main(String[] args) {
        // canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3});

//        maxProfit(new int[]{1, 2});

        Leetcode leetcode = new Leetcode();
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(1);
        treeNode1.right = treeNode2;
//        leetcode.isValidBST(treeNode1);

        //     leetcode.buildTree(new int[]{1, 2, 3, 4, 5, 6}, new int[]{3, 2, 4, 1, 6, 5});

        leetcode.buildTree2(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
    }


    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int g = 0;
        int c = 0;
        int ye = 0;
        int start = -1;
        int j = len;
        for (int i = 0; i < j; i++) {
            g = gas[i];
            c = cost[i];
            if (start > -1) {
                if (ye >= 0)
                    ye += g - c;
                else
                    start = -1;
            } else if (g >= c) {
                start = i;
                ye = g - c;
            }

            if (i + 1 >= len && start > 0) {
                i = -1;
                j = start;
            }


        }
        return ye >= 0 ? start : -1;
    }

    /**
     * 股票最大利益
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
//        int k = 0;
//        int len = prices.length;
//        int[][][] dp = new int[len][k][2];
//        //    写出状态转移
//        for (int i = 0; i < len; ++i) {
//            // 状态转移
//            dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
//            // 当今日选择了买 k-1
//            dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
//        }
//        return dp[len - 1][k-1][0];


// 本例中 k=1,专项优化 7,1,5,3,6,4
        int len = prices.length;
        if (len == 0) return 0;
        //    写出状态转移
        // 对i=0，左特殊处理
        int x = 0, y = Integer.MIN_VALUE;
        for (int i = 0; i < len; ++i) {
            // 状态转移
            x = Math.max(x, y + prices[i]);
            y = Math.max(y, -prices[i]);
        }
        return x;
    }


    Integer last = null;

    /**
     * 校验二叉树搜索
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        return doValid(root);
    }

    boolean doValid(TreeNode node) {
        if (node == null) return true;
        if (node.left != null) {
            boolean dd = doValid(node.left);
            if (!dd) return false;
        }
        int val = node.val;
        if (last != null && val <= last) return false;
        last = val;
        if (node.right != null) {
            boolean dd = doValid(node.right);
            if (!dd) return false;
        }
        return true;
    }


    /**
     *
     */
    LinkedList<TreeNode> q = new LinkedList<TreeNode>();

    List doSumNumbers(TreeNode node) {
        List l = new ArrayList();
        if (node == null) return l;
        q.add(node);
        while (!q.isEmpty()) {
            List list = new ArrayList();
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode poll = q.poll();
                if (poll.left != null)
                    q.add(poll.left);
                if (poll.right != null)
                    q.add(poll.right);
                list.add(poll);

            }
            l.add(list);

        }
        return l;
    }

//    LinkedList<TreeNode> q = new LinkedList<TreeNode>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode node) {
        List l = new ArrayList();
        if (node == null) return l;
        q.add(node);
        boolean isReverser = true;
        while (!q.isEmpty()) {
            List list = new ArrayList();
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode poll = null;
                if (isReverser) {
                    poll = q.poll();
                    if (poll.left != null)
                        q.add(poll.left);
                    if (poll.right != null)
                        q.add(poll.right);

                } else {
                    poll = q.pollLast();

                    if (poll.right != null)
                        q.addFirst(poll.right);
                    if (poll.left != null)
                        q.addFirst(poll.left);
                }
                ;
                list.add(poll.val);
            }
            l.add(list);
            isReverser = !isReverser;

        }
        return l;

    }

    /**
     * BFS重构树
     */

    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //
        this.inorder = inorder;
        this.preorder = preorder;

        TreeNode treeNode = doSumNumbers(0, preorder.length - 1, 0, preorder.length - 1);
        return treeNode;
    }

    TreeNode doSumNumbers(int pStart, int pEnd, int iStart, int iEnd) {
        if (pStart > pEnd || iEnd < iStart) return null;
        int rootVal = preorder[pStart];
        int i = iStart;
        while (i <= iEnd) {
            if (rootVal == inorder[i]) break;
            i++;
        }
        TreeNode root = new TreeNode(rootVal);
        //
        int len = i - iStart;

        root.left = doSumNumbers(pStart + 1, pStart + len, iStart, i);
        root.right = doSumNumbers(pStart + len + 1, pEnd, i + 1, iEnd);
        return root;
    }

    /**
     * BFS交替反向构造树
     */
    int[] postorder;
    //    int[] inorder;
    HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();


    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        //
        int idx = 0;
        for (Integer val : inorder)
            idx_map.put(val, idx++);
        this.inorder = inorder;
        this.postorder = postorder;
        TreeNode treeNode = doWork2(0, postorder.length - 1, 0, postorder.length - 1);
        return treeNode;
    }

    TreeNode doWork2(int pStart, int pEnd, int iStart, int iEnd) {
        if (pStart > pEnd || iEnd < iStart) return null;
        int rootVal = postorder[pEnd];
        int i = idx_map.get(rootVal);

        TreeNode root = new TreeNode(rootVal);
        // 移动长度
        int len = iEnd - i;
        // 左边
        // 注意！！！ 核心问题 left pre的右边界, right 的左边界条件
        root.left = doWork2(pStart, pEnd - len - 1, iStart, i - 1);
        root.right = doWork2(pEnd - len, pEnd - 1, i + 1, iEnd);
        return root;
    }

    /**
     * DFS遍历树,迭代
     */
    void DSF(TreeNode treeNode) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = treeNode;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;

        }
        System.out.println(list);
    }


    /**
     * 二叉树转链表
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        TreeNode pre = null;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
//                优化
                if (pre != null) {
                    pre.left = null;
                    pre.right = cur;
                }

                stack.push(cur.right);
                list.add(cur.val);
                pre = cur;
                cur = cur.left;
                //  temp.left = null;

            }
            cur = stack.pop();

        }
  /*      if (list.size() < 1) return;

        cur = root;
        root.left = null;
        for (int i = 1; i < list.size(); ++i) {
            cur.right = new TreeNode(list.get(i));
            cur = cur.right;
        }
        */


    }

    /**
     * 二叉树转链表，思路问题，2m
     *
     * @param root
     */
    public void flatten02(TreeNode root) {
        this.cur = root;
        if (root == null) return;
        if (root.left != null) {
            DFSRc02(root.left);
            root.left = null;
        }
        if (root.right != null)
            DFSRc02(root.right);
    }

    TreeNode cur = null;

    void DFSRc02(TreeNode treeNode) {
        // res0.add(treeNode.val);
        TreeNode l = treeNode.left;
        TreeNode r = treeNode.right;
        treeNode.left = null;
        cur.right = treeNode;
        cur = cur.right;
        if (l != null) {
            DFSRc02(l);
        }
        if (r != null)
            DFSRc02(r);
    }


    TreeNode pre = null;

    /**
     * 采用后序，pre 逆保存解决 1ms
     *
     * @param root
     */
    public void flatten03(TreeNode root) {
        if (root == null)
            return;
        flatten03(root.right);
        flatten03(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }

    /**
     * 将每一层的节点连起来子类
     */

    /**
     * 满二叉树 time 3ms
     *
     * @param root
     * @return
     */
    public Node connect01(Node root) {
        if (root == null) return null;
        List<Node> list = new LinkedList<>();
        list.add(root);
        int j = 0;
        int i = 0;
        while (list.size() > 0) {
            i = j << 1;
            j++;
            Node pre = null;
            boolean b = false;
            while (i > 0) {
                Node node = list.remove(0);
                if (pre != null) pre.next = node;
                if (node.left != null) {
                    list.add(node.left);
                    list.add(node.right);
                    b = true;
                }
                i--;
                pre = node;
            }
            if (b) break;
        }
        return root;
    }

    /**
     * time 0ms
     *
     * @param root
     * @return
     */
    public Node connect02(Node root) {
        if (root == null) return null;
        Node head = root;
        // 判断其left 很细节，因为要去下一层寻找
        while (head.left != null) {
            Node temp = head;

            while (temp != null) {
                temp.left.next = temp.right;
                if (temp.next != null)
                    temp.right.next = temp.next.left;
                temp = temp.next;
            }
            //
            head = head.left;
        }
        return root;
    }


    int sum = 0;

    /**
     * 从跟节点到叶子节点所组成的树累加,核心思想从上倒下
     *
     * @param root
     * @return {@see int}
     */
    public int sumNumbers(TreeNode root) {
        doSumNumbers(root, 0);
        return sum;

    }

    void doSumNumbers(TreeNode root, int cur) {
        if (root == null) return;
        // 核心一部分 1
        int t = cur * 10 + root.val;
        if (root.left == null && root.right == null) {
            // 核心部分 2
            sum += t;
            return;
        }
        // 核心部分 3
        doSumNumbers(root.left, t);
        doSumNumbers(root.right, t);

    }

    /**
     * 填充每个节点的下一个右侧节点指针 II
     * <p>
     * BFS 迭代3ms，经过一、二优化后控制到了 2ms
     * <p>
     * BFS 递归1ms
     *
     * @param root
     * @return
     */
    public Node connect03(Node root) {
        if (root == null) return root;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (q.size() > 0) {
            int size = q.size();
            int i = size;
            while (i > 0) {
                // 优化方案一： poll()替代remove()
                Node node = q.poll();
                // 优化方案而 ： 直接peek()比较，无需保存前一饿节点
                if (i < size - 1)
                    node.next = q.peek();

                if (node.left != null)
                    q.add(node.left);

                if (node.right != null)
                    q.add(node.right);
                i--;
            }
        }
        return root;
    }

    /**
     * 填充每个节点的下一个右侧节点指针 II
     * 终极优化版 0ms
     *
     * @param root
     * @return
     */
    public Node connectOptimism(Node root) {
        if (root == null || (root.right == null && root.left == null)) {
            return root;
        }
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            root.right.next = getNextNoNullChild(root);
        }
        if (root.left == null) {
            root.right.next = getNextNoNullChild(root);
        }
        if (root.right == null) {
            root.left.next = getNextNoNullChild(root);
        }

        //这里要注意：先递归右子树，否则右子树根节点next关系没建立好，左子树到右子树子节点无法正确挂载
        root.right = connectOptimism(root.right);
        root.left = connectOptimism(root.left);

        return root;
    }

    private static Node getNextNoNullChild(Node root) {
        while (root.next != null) {
            if (root.next.left != null) {
                return root.next.left;
            }
            if (root.next.right != null) {
                return root.next.right;
            }
            root = root.next;
        }
        return null;
    }

    /**
     * 173.题感悟
     * {@link Stack}        默认栈，vector的子类，push() 有锁
     * {@link LinkedList}   继承Queue与AbstractList、Queue add()会将值包装成额你不元素
     * {@link Deque}        继承Queue 双向队列,ArrayDeque add() 无锁，其他并发包的都有锁的实现
     */



}


